package DP.背包.每样1个;

import org.junit.Test;

/**
 * 思路：
 *     纯汉译 DP
 *
 * forj 为什么不用 s/2 -> r[0] ？
 *      -> 答：
 *            因为 上方 w总个数 不好处理
 *            <=N-1 ？
 *
 * 所以 -> 改用 sum计算
 *      s/2 只在最后 r res 用
 *
 */
public class 分割等和子集416 {
    public boolean canPartition(int[] w) {
        int sum = 0;
        for (int i : w) {
            sum += i;
        }
        if(sum%2==1)return false; // 奇数和 不可能2分

        boolean[][] dp = new boolean[w.length + 1][sum +  1];

        // 外初 - 特殊值
        for (int preNum = 0; preNum < dp.length; preNum++) {
            for (int reW = 0; reW < dp[0].length; reW++) {
                if(preNum==0){
                    dp[0][reW] = false;
                    continue;
                }else if(reW == 0){
                    dp[preNum][0] = true;
                    continue;
                }
            }
        }

        // 双1
        for (int preNum = 1; preNum <= w.length; preNum++) {
            for (int reW = 1; reW <= sum; reW++) {
                int cI = preNum-1;
                if(reW >= w[cI]){
                    //           下一个                    &   当前
                    boolean na = dp[preNum-1][reW-w[cI]] && true;
                    boolean buna = dp[preNum-1][reW];
                    dp[preNum][reW] = na || buna; // max 改 ||
                }else {
                    boolean buna = dp[preNum-1][reW];
                    dp[preNum][reW] = buna;
                }
            }
        }

        int halfSum = sum /2 ;
        return dp[w.length][halfSum];
    }

    @Test
    public void test() {
        int[] p = new int[]{1,5,11,5};
        System.out.println("RES:" + canPartition(p));
    }
}
